package linearList;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

public class SeqList<T> implements List<T> {
    private Object[] elements;
    private int length;

    public SeqList() {
        this(8);
    }

    public SeqList(int length) {
        this.elements = new Object[length];
        this.length = 0;
    }

    public SeqList(T[] data) {
        this.elements = new Object[data.length];
        for(int i = 0; i < data.length; i++) {
            this.elements[i] = data[i];
        }

        this.length = data.length;
    }

    @Override
    public boolean isEmpty() {
        return this.length == 0;
    }

    @Override
    public boolean contains(Object o) {
        return false;
    }

    @Override
    public Iterator<T> iterator() {
        return null;
    }

    @Override
    public Object[] toArray() {
        return new Object[0];
    }

    @Override
    public <T1> T1[] toArray(T1[] a) {
        return null;
    }

    @Override
    public boolean add(T t) {
        return false;
    }

    @Override
    public boolean remove(Object o) {
        return false;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return false;
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {
        return false;
    }

    @Override
    public boolean addAll(int index, Collection<? extends T> c) {
        return false;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return false;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return false;
    }

    @Override
    public int size() {
        return this.length;
    }

    @Override
    public T get(int i) {
        if (i >=0 && i < this.length) {
            return (T)this.elements[i];
        }

        return null;
    }

    @Override
    public T set(int i, T x) {
        if (x == null) {
            System.out.println("invalid param x in set(i,x): null");
            return x;
        }

        if (i >=0 && i < this.length) {
            this.elements[i] = x;
        }
        return x;
    }

    @Override
    public void add(int index, T element) {

    }


    public int insert(int i, T x) {
        if (x == null) {
            System.out.println("invalid param x in set(i,x): null");
            return -1;
        }

        // 参数校验
        if (i < 0 || i > this.length) {
            System.out.println("invalid param i in set(i,x)");
            return -1;
        }

        // 判断是否需要扩容
        // copy 0 ~ i-1 元素
        Object[] source = this.elements;
        if (this.length == this.elements.length) {
            this.elements = new Object[source.length * 2];
            for (int j = 0; j < i; j++) {
                this.elements[j] = source[j];
            }
        }

        // i之后的元素向后移动
        for (int k = this.length - 1; k >= i; k--) {
            this.elements[k + 1] = source[k];
        }

        // 设置 i 元素
        this.elements[i] = x;

        this.length++;
        return i;
    }


    public int insert(T x) {
        return this.insert(this.length, x);
    }

    @Override
    public T remove(int i) {
        if (i >= 0 && i < this.length) {
            T old = (T)this.elements[i];
            for (int j = i + 1; j <= this.length - 1; j++) {
                this.elements[j - 1] = this.elements[j];
            }
            this.length--;
            return old;
        }
        return null;
    }

    @Override
    public int indexOf(Object o) {
        return 0;
    }

    @Override
    public int lastIndexOf(Object o) {
        return 0;
    }

    @Override
    public ListIterator<T> listIterator() {
        return null;
    }

    @Override
    public ListIterator<T> listIterator(int index) {
        return null;
    }

    @Override
    public List<T> subList(int fromIndex, int toIndex) {
        return null;
    }

    public int search(T key) {
        for (int i = 0; i < this.length; i++) {
            if (key.equals(this.elements[i])) {
                return i;
            }
        }

        return -1;
    }


    public T removeByKey(T key) {
        return this.remove(this.search(key));
    }

    @Override
    public void clear() {
        //设置长度为0，未释放数组空间
        this.length = 0;
    }

    public String toString() {
        String s = "顺序表，长度=" + this.length
                + ", 容量=" +this.elements.length
                + ", 内容如下: ";
        s = s + "(";
        for (int i = 0; i < this.length; i++) {
            if (i > 0) {
                s = s + ",";
            }
            s = s + elements[i];
        }
        s = s + ")";
        return s;
    }

    public static void main(String[] args) {
        System.out.println("--测试初始化--");
        Integer[] data = {66, 33, 15, 11, 78, 4, 6, 9, 6, 10};
        SeqList<Integer> seqList = new SeqList<Integer>(data);
        System.out.println(seqList);

        System.out.println("--测试insert(2, 22)--");
        seqList.insert(2, 22);
        System.out.println(seqList);

        System.out.println("--测试insert 10个元素--");
        for (int i = 20; i <= 30; i++) {
            seqList.insert(i);
        }
        System.out.println(seqList);

        System.out.println("--测试remove index为5的元素--");
        seqList.remove(5);
        System.out.println(seqList);

        System.out.println("--测试获取 index为5的元素--");
        System.out.println(seqList.get(5));

        System.out.println("--测试设置 index为5的元素为100--");
        seqList.set(5, 100);
        System.out.println(seqList);

        System.out.println("--测试查找元素等于100的索引--");
        System.out.println(seqList.search(100));

        System.out.println("--测试remove by key, 删除100--");
        seqList.removeByKey(new Integer(100));
        System.out.println(seqList);

    }
}

